/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2022-10-17
 * Time: 21:57
 */
public class MyBinarySearchTree {

    static class TreeNode {
        public int val;  // 节点值
        public TreeNode left; // 左节点
        public TreeNode right;  // 右节点

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root; // 根节点

    /**
     * 搜索二叉树中是否存在某个值
     *
     * @param key
     * @return
     */
    public TreeNode search(int key) {
        TreeNode cur = root;
        if (cur == null) {
            return null;
        }
        while (cur != null) {
            if (cur.val < key) {
                cur = cur.right;
            } else if (cur.val > key) {
                cur = cur.left;
            } else {
                return cur;
            }
        }
        return null;
    }

    /**
     * 插入一个值为 key 得节点
     *
     * @param key
     * @return
     */
    public boolean insert(int key) {
        TreeNode cur = root;
        if (cur == null) {
            root = new TreeNode(key);
            return true;
        }

        // 记录cur得前一个父亲节点
        TreeNode parents = null;
        while (cur != null) {
            parents = cur;
            if (cur.val < key) {
                cur = cur.right;
            } else if (cur.val > key) {
                cur = cur.left;
            } else {
                // 由搜索树性质相同节点无法插入
                return false;
            }
        }
        // 此时cur为空
        if (parents.val < key) {
            parents.right = new TreeNode(key);
        } else {
            parents.left = new TreeNode(key);
        }
        return true;
    }


    /**
     * 中序遍历
     *
     * @param root
     */
    private void inoder(TreeNode root) {
        if (root == null) {
            return;
        }
        inoder(root.left);
        System.out.print(root.val + " ");
        inoder(root.right);
    }

    /**
     * 删除值为 key得节点
     *
     * @param key
     */
    public void delete(int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        if (root == null) {
            throw new EmptyException("搜索树为空，无法删除！");
        }
        while (cur != null) {
            parent = cur;
            if (cur.val == key) {
                deleteNode(parent,cur);
            } else if (cur.val < key) {
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }

    }

    private void deleteNode(TreeNode parent, TreeNode cur) {
        //1. 要删除的节点没有左树
        if (cur.left == null) {
            if (cur == root) {
                root = parent.right;
            } else if (cur == parent.left) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }

        } else if (cur.right == null) {
            // 2. 要删除的节点没有右树
            if(cur == root) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
        } else {

            // 要删除的节点为叶子节点
            // 去要删除得节点得左树节点寻找比此时节点大得右树节点
            TreeNode tmp = cur.left;
            TreeNode prev = cur;
            while(tmp.right != null) {
                prev = tmp;
                tmp = tmp.right;
            }
            // 交换要删除得值和当前tmp得右树节点
            cur.val = tmp.val;
            // 删除当前tmp得值

            // 当寻找到后得左树得最大值只有一个结点时
            if(tmp == prev.right) {
                prev.right = tmp.left;
            }else {
                // tmp == prev.left
                prev.left = tmp.left;
            }
        }
    }


    public static void main(String[] args) {
        int[] array = {5, 3, 4, 1, 7, 8, 2, 6, 0, 9};
        MyBinarySearchTree myBinarySearchTree = new MyBinarySearchTree();
        for (int i = 0; i < array.length; i++) {
            myBinarySearchTree.insert(array[i]);
        }
        myBinarySearchTree.inoder(myBinarySearchTree.root);

        myBinarySearchTree.delete(1);
        System.out.println("==========");
        myBinarySearchTree.inoder(myBinarySearchTree.root);


    }
}


